package com.ljy.my_study.lintcode.子树;

import com.ljy.my_study.util.TreeNodeUtil;
import com.ljy.my_study.util.TreeNodeUtil.TreeNode;

/** 
* @author James
* @date 2018年9月29日 
*/
public class TestMain {
//	描述
//	有两个不同大小的二叉树： T1 有上百万的节点； T2 有好几百的节点。请设计一种算法，判定 T2 是否为 T1的子树。
//
//	若 T1 中存在从节点 n 开始的子树与 T2 相同，我们称 T2 是 T1 的子树。也就是说，如果在 T1 节点 n 处将树砍断，砍断的部分将与 T2 完全相同。
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	下面的例子中 T2 是 T1 的子树：
//
//	       1                3
//	      / \              / 
//	T1 = 2   3      T2 =  4
//	        /
//	       4
//	下面的例子中 T2 不是 T1 的子树：
//
//	       1               3
//	      / \               \
//	T1 = 2   3       T2 =    4
//	        /
//	       4
	public static void main(String[] args) {
		TreeNode T1=TreeNodeUtil.deserialize("1,1,1,2,3,#,2,#,#,4,5,3");
		TreeNode T2=TreeNodeUtil.deserialize("1,2,3,#,#,4,5");
		System.out.println(isSubtree(T1,T2));
	}
	public static boolean isSubtree(TreeNode T1, TreeNode T2) {
		if(T1==null&&T2==null) {
			return true;
		}else if(T1==null&&T2!=null) {
			return false;
		}else if(T1!=null&&T2==null) {
			return true;
		}
		if(isSame(T1,T2)) {
			return true;
		}else {
			return isSubtree(T1.left,T2)||isSubtree(T1.right,T2);
		}
	}
	
	public static boolean isSame(TreeNode T1,TreeNode T2) {
		if(T1==null&&T2==null) return true;
		if((T1==null&&T2!=null)||(T1!=null&&T2==null)) return false;
		if(T1.val==T2.val) {
			return isSame(T1.left,T2.left)&&isSame(T1.right,T2.right);
		}else {
			return false;
		}
	}
}
